HW#2 --- last modified March 02 2019 17:19:32..

Solution set.

Due date: Mar 15

Files to be submitted:
  cs156-checkers-move.scm

Purpose: To get familiar with adversarial search problems. To learn about AI for logical agents

Specification:

The suggested study problems for this assignment are: 7.9, 7.10, 7.17 You do not need to turn these in.

For this homework you need to write a Scheme function cs156-checkers-move. This functions is supposed to compute the next move in a game of CS156 Checkers. CS156 Checkers is a variant of Chinese checkers played on a board consisting of three rows of nine columns each. Each square on this board has either a 0, 1 or 2 on it. A 0 represents the square is unoccupied a 1 indicates Player 1 has a piece on that square, and a 2 indicates Player 2 has a piece on that square. Boards are represented in Scheme using a list of three lists. The representation of the start of game board is:

((1 1 1 0 0 0 2 2 2)

(1 1 1 0 0 0 2 2 2)

(1 1 1 0 0 0 2 2 2))

Player 1 goes first. Each player's objective is to move all his/her pieces to the opposite side of the board. For example,

((2 2 2 0 1 1 1 1 0)

(2 2 2 0 0 0 1 1 0)

(2 2 2 0 0 0 1 1 1))

is a winning board for Player 2. In one turn a player is allowed to move any of his pieces in the direction towards winning (for that player) one square or up and down one square provided the square moved to is unoccupied. In addition, one is allowed to move a piece by hopping over one occupied square (occupied by either side) to an unoccupied square. If from this new position another hop by the same piece is possible than one can do that hop as well in the same turn. All hops must be in the vertical direction or towards the win position for that player. A move is represented by a list consisting of a single step move or a list consisting of a sequence of hops. For a single step move the format is, (row-start column-start row-move-to column-move-to). Row and columns start with count 0. For a hop move the format is (row-start col-start row-next1 col-next1 ... row-final-move-to col-final-move-to)

For example, the move (1 2 1 3) by Player 1 on the start of game board results in:

((1 1 1 0 0 0 2 2 2)

(1 1 0 1 0 0 2 2 2)

(1 1 1 0 0 0 2 2 2))

If Player 2 then moved (0 6 0 5) and Player 1 responded (1 0 1 2 1 4), the board would look like:

((1 1 1 0 0 2 0 2 2)

(0 1 0 1 1 0 2 2 2)

(1 1 1 0 0 0 2 2 2))

Your function should take as input a list (player_num board) and output a list (move resulting-board). Outputs not matching this format or illegal moves are considered equivalent to forfeiting the game. (It might be the case that a player has no next move, in which case that player loses.) Your function cs156-checkers-move should make nontrivial use of the minimax algorithm with alpha-beta pruning from class to be considered for the tournament. Programs will be alotted a maximum of 10 seconds on my 1.1Ghz E-machine to compute a next move (taking longer is considered as forfeiting.) The programs from the class will be divided into 4 leagues. Within each league a round robin tournament will be played. (Each pair of programs will play each other as both Player one and as Player 2.) Winning a match increases a program 1 point in the league standings. After all league games have been played, the winner of each league will received 7 points towards their homework, the runner-up 6 and so on. After the league winners have been determined there will be a semi-final and finals matches to determine the best among these four programs. The top program will receive +2 bonus points. The silver and bronze program will receive +1 bonus points.

Here is a some code useful for testing your agents:

;;;;
;;;;Code to play two agents against each other at cs156-checkers
;;;;
;;;;The main function below is play-game. This takes two agents and plays
;;;; a game of cs156-checkers between them.
;;;;
;;;;The function human-agent is defined so people can play the game as well as computers.
;;;;
;;;;The function human-game can be invoke so two humans can play each other
;;;;
;;;;To test this out, at the the prompt type (human-game)


;;;
;;;function to set the n element of a list
;;;
(define set-ref!
  (lambda (list n new)
    (if (= n 0)
        (set-car! list new)
        (set-ref! (cdr list) (- n 1) new))))

;;;
;;;function to shallow copy a list
;;;
(define copy-list
  (lambda (list)
    (if (null? list)
        ()
        (cons (car list) (copy-list (cdr list))))))

;;;
;;;function to get a list of the first number elements from a lsit
;;;
(define list-head
  (lambda (list number)
    (if (= number 0)
        '()
        (cons (car list) (list-head (cdr list) (- number 1))))))

;;;
;;;function to copy a cs156-checker board
;;;
(define copy-board
  (lambda (board)
    (let ((row1 (copy-list (car board)))
          (row2 (copy-list (cadr board)))
          (row3 (copy-list (caddr board))))
      (list row1 row2 row3))))

;;;
;;;function to set the x y location of a board to a given value
;;;
(define update-square-board!
  (lambda (board x y value)
    (let* ((row (car (list-tail board x)))
           (col (list-tail row y)))
      (set-car! col value))))

;;;
;;;function to get what piece, if any, is on the (x, y) square on the
;;; board
;;;
(define get-square-board
  (lambda (board x y)
    (let* ((row (car (list-tail board x))))
      (list-ref row y))))

;;;function to produce the board that results from a given move
;;;
;;;Parameters
;;;
;;; move - a list consisting of steps of move
;;;
;;; board - to do move on
;;;
;;; returns - resulting board

(define apply-move
  (lambda (move board)
    (let* ((next-board (copy-board board))
          (start-x (car move))
          (start-y (cadr move))
          (l (length move))
          (end-x (list-ref move (- l 2)))
          (end-y (list-ref move (- l 1)))
          (piece (get-square-board board start-x start-y)))
      (update-square-board! next-board start-x start-y 0)
      (update-square-board! next-board end-x end-y piece)
      next-board)))

;;;
;;;functions used to draw all or parts of a board
;;;
(define draw-row
  (lambda (x)
    (display " ")
    (if (null? x)
        (newline)
        (begin
          (display (car x))
          (draw-row (cdr x))))))

(define draw-board
  (lambda (board)
    (draw-row (car board))
    (draw-row (cadr board))
    (draw-row (caddr board))))


;;;
;;;function to get a move from a human player and make it into the format
;;; expected of an agent
;;;
;;;Parameters
;;;
;;; state - expected to be in the form (turn board) where turn is which
;;;         player's turn and board is the board player gets to move on
;;;
;;; returns - a list consisting of (move resulting-board)
(define human-agent
  (lambda (state)
      (display "You are player ")
      (display (car state))
      (display ".\n\nHere is the current board:\n")
      (draw-board (cadr state))
      (let* ((move (read))
             (next-board (apply-move move (cadr state))))
        (list move next-board))))

;;;
;;;Next functions all used to check if a move is valid
;;; tried to make sure valid-move-board? will give a #t or #f answer
;;; rather than through an error
;;;
(define on-board-coord?
  (lambda (x y)
    (and (integer? x) (integer? y)
        (>= x 0) (< x 3)
        (>= y 0) (< y 9))))



(define valid-step-move?
  (lambda (board move)
    (if (not (= (length move) 4))
        #f
        (let* ((start-x (car move))
              (start-y (cadr move))
              (end-x (caddr move))
              (end-y (cadddr move))
              (piece (get-square-board board start-x start-y)))

          (if (or (not (on-board-coord? start-x start-y))
                  (not (on-board-coord? end-x end-y))
                  (= piece 0) )
              #f
              (and (or (and (= start-x end-x) (= end-y (+ start-y 1)) (= piece 1))
                       (and (= start-x end-x) (= end-y (- start-y 1)) (= piece 2))
                       (and (= start-y end-y) (= (abs (- end-x start-x)) 1)))
                  (= (get-square-board board end-x end-y) 0)))))))

(define valid-jump-move?
  (lambda (board move)
    (let* ((start-x (car move))
          (start-y (cadr move))
          (end-x (caddr move))
          (end-y (cadddr move))
          (mid-x (/ (+ start-x end-x) 2))
          (mid-y (/ (+ start-y end-y) 2))
          (piece (get-square-board board start-x start-y)))
      (if (or (not (on-board-coord? start-x start-y))
              (not (on-board-coord? end-x end-y))
              (= piece 0) )
          #f
          (let ((hop-ok-boolean
                (and (or (and (= start-x end-x) (= end-y (+ start-y 2)) (= piece 1))
                         (and (= start-x end-x) (= end-y (- start-y 2)) (= piece 2))
                         (and (= start-y end-y) (not (= end-x start-x)) (not (= start-x 1))))
                     (= (get-square-board board end-x end-y) 0)
                     (> (get-square-board board mid-x mid-y) 0))))
            (if (or (= (length move) 4) (not hop-ok-boolean))
                hop-ok-boolean
                (valid-jump-move? (apply-move (list start-x start-y end-x end-y) board) (cddr move))))))))

(define valid-move?
  (lambda (board move)
    (if (or (not (list? move)) (not (>= (length move) 4))
            (not (even? (length move))))
        #f
        (or (valid-step-move? board move)
            (valid-jump-move? board move)))))


(define valid-squares-count?
  (lambda (list count)
    (if (null? list)
        (= count 999)
        (let ((f (car list))
              (next-count count))
          (if (not (integer? f))
              #f
              (begin
                (cond ((= f 0) (set! next-count (+ next-count 1)))
                      ((= f 1) (set! next-count (+ next-count 10)))
                      ((= f 2) (set! next-count (+ next-count 100))))
                (valid-squares-count? (cdr list) next-count)))))))

(define valid-board?
  (lambda (board)
    (if (or (not (list? board)) (not (= (length board) 3)))
        #f
        (let ((row1 (car board))
              (row2 (cadr board))
              (row3 (caddr board)))
          (if (or (not (= (length row1) 9)) (not (= (length row2) 9))
                  (not (= (length row3) 9)))
              #f
              (valid-squares-count? (append row1 row2 row3) 0))))))

(define valid-move-board?
  (lambda (board move-board)
    (if (or (not (list? move-board)) (not (= (length move-board) 2)))
         #f
         (let ((next-board (cadr move-board))
               (move (car move-board)))
           (and (valid-move? board move) (valid-board? next-board)
                (equal? next-board (apply-move move board)))))))

;;;
;;; function to compute half of a round in the game less checking for a win
;;;
(define get-check-and-apply-move
  (lambda (agent-move turn board)
   (let ((move-board (agent-move (list turn board))))
      (if (valid-move-board? board move-board)
          (cadr move-board)
          (error 'get-check-and-apply-move "player ~s loses because made
illegal move. " turn)))))


;;;
;;; functions to check for a win
;;;
(define player2-win-board?
  (lambda (board)
    (let* ((row1 (list-head (car board) 3))
          (row2 (list-head (cadr board) 3))
          (row3 (list-head (caddr board) 3))
          (single-list (cons 2 (append row1 row2 row3))))
          (apply = single-list))))

(define player1-win-board?
  (lambda (board)
    (let* ((row1 (list-tail (car board) 6))
          (row2 (list-tail(cadr board) 6))
          (row3 (list-tail (caddr board) 6))
          (single-list (cons 1 (append row1 row2 row3))))
          (apply = single-list))))

(define game-over?
  (lambda (board)
    (or (player1-win-board? board) (player2-win-board? board))))

(define display-win
  (lambda (winner)
    (begin
      (display "\n\nPlayer ")
      (display winner)
      (display " wins!!\n\n"))))

;;;
;;; constant for initial board
;;;
(define initial-board
  (list
   (list 1 1 1 0 0 0 2 2 2)
   (list 1 1 1 0 0 0 2 2 2)
   (list 1 1 1 0 0 0 2 2 2)))

;;;
;;;functions to play game
;;;

(define play-game-turn
  (lambda (cur-agent-move other-agent-move turn board)
    (let ((next-board (get-check-and-apply-move cur-agent-move turn board))
          (next-turn (if (= turn 1) 2 1)))
      (if (game-over? next-board)
          (display-win turn)
          (play-game-turn other-agent-move cur-agent-move next-turn
next-board)))))


(define play-game
  (lambda (agent1-move agent2-move)
    (play-game-turn agent1-move agent2-move 1 initial-board)))

(define human-game
  (lambda ()
    (play-game human-agent human-agent)))

Point Breakdown